1. Field of the Invention.
The present invention generally relates to contention-free access and management in multiprocessing software environments. In particular, the invention provides contention-free access to timer objects in a multiprocessing environment.
2. Description of Related Art.
A common operation in computer software is the scheduling of work to be performed at some time in the future, such as 10 milliseconds from the current time. Typically, this is accomplished by the use of a timer object. The operating system provides the timer object and the timer object schedules work by keeping track of elapsed time.
In the general case, the software using the timer performs a sequence of steps. The software first requests a timer object from the operating system. The software initializes the timer object, specifying the duration before the timer expires. The software then waits, or "blocks", on the timer object until the time duration has elapsed. When the operating system determines that the specified duration has elapsed, the previously blocked software performs its defined tasks.
In multithreaded, multiprocessing, or multiprogrammed environments, it often happens that there is a need to schedule work to be performed by a plurality of threads, processes, or jobs at some time in the future. If the threads are intended to block for the same duration of time, the threads may block on the same timer object, thereby reducing resource consumption and processing overhead. However, management of the shared timer may be costly, since ordinarily each thread will contend for access to the timer object and re-initialize it for the next timer interval. Notably, many of the traditional shared-timer management techniques are costly, including the "mutex and master thread" approach; the "mutex: first thread in initializes the timer" approach; and the "spinlock" approach (in multiprocessing systems).
In the "mutex and master thread" approach, a mutex is a synchronization object that ensures exclusive access to a resource. Other threads requesting the mutex have to wait until the mutex is signaled. The master thread is responsible for initializing the timer.
The master thread follows the procedure outlined below. First, it initializes the timer with the next duration and signals the operating system mutex, allowing all threads to run. The non-master threads may now block on the timer. After all non-master threads have gotten through the mutex, then the master thread resets the mutex so that any further waiting threads will block. If a thread is not a master thread, then it skips the above procedure and waits on the mutex.
In the "mutex: first thread in initializes the timer" approach, the first thread has the responsibility for setting the timer. The first thread acquires the operating system mutex and determines whether the timer is already set. If the timer is set, the first thread releases the mutex. Otherwise, the first thread initializes the timer and then releases the mutex. In either case, the thread subsequently blocks on the timer.
In the "spinlock" approach (in multiprocessing systems), a spinlock variable is associated with the timer. A thread attempts to acquire the spinlock variable, using an interlocked test and set operation . After acquiring the spinlock variable, the thread then determines whether the timer has been set. If the timer has not been set, the thread initializes the timer and releases the spinlock variable. In either case, it blocks on the timer object.
One problem with these traditional approaches is that they require a large amount of processing overhead because each thread must contend for exclusive to the timer. Additionally, these methods increase the elapsed time of the operation, since each thread must wait (either spinning or blocking) until it acquires exclusive access to the timer object.
Thus, because of the processing overhead of traditional methods, there is a need for an invention that eliminates the contention for timer-objects and the need for synchronization mechanisms and subsequent wait times.